package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class P382LinkedListRandomNode {
    public static void main(String[] args) {

        P382LinkedListRandomNode solution = new P382LinkedListRandomNode();
        ListNode listNode = solution.new ListNode(1);
        listNode.next = solution.new ListNode(2);
        listNode.next.next  = solution.new ListNode(3);
        Solution solution1 = solution.new Solution(listNode);
        System.out.println(solution1.getRandom());

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        List<ListNode> list = new ArrayList<>();

        public Solution(ListNode head) {
            while (head != null) {
                list.add(head);
                head = head.next;
            }
        }

        public int getRandom() {
            int size = list.size();
            Random random = new Random();
            int i = random.nextInt(size);
            ListNode listNode = list.get(i);
            return listNode.val;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}